package 回溯;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 组合总和II216.java
 * @createTime 2023年01月07日 14:06:00
 */
public class 组合总和II216 {
	List<List<Integer>> result = new ArrayList<>();

	public List<List<Integer>> combinationSum3(int k, int n) {
		backTrace(k, n, new boolean[9], 0, 0);
		return result;
	}

	LinkedList<Integer> temp = new LinkedList<>();

	public void backTrace(int k, int n, boolean[] used, int sum, int curIndex) {
		//复合要求
		if (temp.size() == k && sum == n) {
			result.add(new ArrayList<>(temp));
			return;
		}
		//遍历到的+当前的已经大于目标
		if (sum >= n) {
			return;
		}
		for (int i = curIndex; i < used.length; i++) {
			//当前的数已经被使用户
			if (used[i]) {
				continue;
			}
			if (sum + i+1 > n) {
				continue;
			}
			temp.add(i+1);
			sum += i+1;
			used[i] = true;
			backTrace(k, n, used, sum, i);
			used[i] = false;
			sum -= i+1;
			temp.removeLast();
		}
	}
}
